package com.duoduo.剑指Offer;

import com.duoduo.Node;

/**
 * @program: algorithm
 * @description: 二叉搜索树与双向链表32
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 * @author: chaidl  ！
 * @create: 2022-05-26 21:50
 */
//TODO  这个是必须要掌握的
public class 二叉搜索树与双向链表32 {
	Node pre, head;
	
	public Node treeToDoublyList(Node root) {
		if (root == null) {
			return null;
		}
		dfs(root);
		head.left = pre;
		pre.right = head;
		return head;
	}
	
	private void dfs(Node root) {
		if (root == null) {
			return;
		}
		dfs(root.left);
		//	到这里说明已经找到最左下角的数字也就是找到第一个数字了
		//	如果pre为空，表示第一个
		if (pre == null) {
			head = root;
		} else if (pre != null) {
			// 如果不为空，那就说明是中间的节点。并且pre保存的是上一个节点，
			// 让上一个节点的右指针指向当前节点
			pre.right = root;
		}
		// 再让当前节点的左指针指向父节点，也就连成了双向链表
		root.left = pre;
		// 保存当前节点，用于下层递归创建
		pre = root;
		dfs(root.right);
	}
}

